package util;

import bean.SelectBean;

import java.util.*;

/**
 * 聚类算法
 */
public class KMeans {
    private int k;// 分成多少簇
    private int m;// 迭代次数
    private int dataSetLength;// 数据集元素个数，即数据集的长度
    private ArrayList<Integer[]> dataSet;// 数据集链表
    private ArrayList<Integer[]> center;// 中心链表
    private ArrayList<ArrayList<Integer[]>> cluster; // 簇
    private ArrayList<Integer> jc;// 误差平方和，k越接近dataSetLength，误差越小
    private Random random;
    BaseDAO dao = new BaseDAO();
    SelectBean sb = new SelectBean();

    /**
     * 设置需分组的原始数据集
     *
     * @param dataSet
     */

    public void setDataSet(ArrayList<Integer[]> dataSet) {
        this.dataSet = dataSet;
    }

    /**
     * 获取结果分组
     */
    public ArrayList<ArrayList<Integer[]>> getCluster() {
        return cluster;
    }

    /**
     * 构造函数，传入需要分成的簇数量
     */
    public KMeans() {
    }

    public KMeans(int k) {
        if (k <= 0) {
            k = 1;
        }
        this.k = k;
    }

    //初始化
    private void init() {
        m = 0;
        random = new Random();
        if (dataSet == null || dataSet.size() == 0) {
            initDataSet();
        }
        dataSetLength = dataSet.size();
        // 若k大于数据源的长度时，置为数据源的长度
        if (k > dataSetLength) {
            k = dataSetLength;
        }
        center = initCenters();// 初始化中心
        cluster = initCluster();// 初始化簇集，分配内存，但元素为空
        jc = new ArrayList<Integer>();// 初始化误差平方和
    }

    /**
     * 如果调用者未初始化数据集，则采用内部测试数据集
     */
    private void initDataSet() {
        dataSet = new ArrayList<Integer[]>();
        Integer[][] dataSetArray = new Integer[][]{{8, 2}, {3, 4}, {2, 5},
                {4, 2}, {7, 3}, {6, 2}, {4, 7}, {6, 3}, {5, 3},
                {6, 3}, {6, 9}, {1, 6}, {3, 9}, {4, 1}, {8, 6}};

        for (int i = 0; i < dataSetArray.length; i++) {
            dataSet.add(dataSetArray[i]);
        }
    }

    /**
     * 初始化中心数据链表，分成多少簇就有多少个中心点
     *
     * @return 中心点集
     */
    private ArrayList<Integer[]> initCenters() {
        ArrayList<Integer[]> center = new ArrayList<Integer[]>();
        int[] randoms = new int[k];
        boolean flag;
        // 生成k个互补相同的随机数
        int temp = random.nextInt(dataSetLength);
        randoms[0] = temp;
        for (int i = 1; i < k; i++) {
            flag = true;
            while (flag) {
                temp = random.nextInt(dataSetLength);
                int j = 0;
                while (j < i) {
                    if (temp == randoms[j]) {
                        break;
                    }
                    j++;
                }
                if (j == i) {
                    flag = false;
                }
            }
            randoms[i] = temp;
        }
        // 生成初始化中心链表
        for (int i = 0; i < k; i++) {
            center.add(dataSet.get(randoms[i]));
        }
        return center;
    }

    /**
     * 初始化簇集合
     *
     * @return 一个分为k簇的空数据的簇集合
     */
    private ArrayList<ArrayList<Integer[]>> initCluster() {
        ArrayList<ArrayList<Integer[]>> cluster = new ArrayList<ArrayList<Integer[]>>();
        for (int i = 0; i < k; i++) {
            cluster.add(new ArrayList<Integer[]>());
        }
        return cluster;
    }

    /**
     * 计算两个点之间的距离(欧几里得距离)
     *
     * @param element 点1
     * @param center  点2
     * @return 距离
     */
    private Integer distance(Integer[] element, Integer[] center) {
        Integer distance = 0;
        Integer x = element[0] - center[0];
        Integer y = element[1] - center[1];
        Integer z = x * x + y * y;
        distance = (int) Math.sqrt(z);
        return distance;
    }

    /**
     * 获取距离集合中最小距离的位置
     * 距离数组
     *
     * @return 最小距离在距离数组中的位置
     */
    private int minDistance(Integer[] distance) {
        Integer minDistance = distance[0];
        int minLocation = 0;
        for (int i = 1; i < distance.length; i++) {
            if (distance[i] < minDistance) {
                minDistance = distance[i];
                minLocation = i;
            } else if (distance[i] == minDistance) // 如果相等，随机返回一个位置
            {
                if (random.nextInt(10) < 5) {
                    minLocation = i;
                }
            }
        }

        return minLocation;
    }

    /**
     * 核心 计算两点之间的距离，并将当前元素放到最小距离中心的簇中
     */
    private void clusterSet() {
        Integer[] distance = new Integer[k];
        for (int i = 0; i < dataSetLength; i++) {
            for (int j = 0; j < k; j++) {
                distance[j] = distance(dataSet.get(i), center.get(j));// 计算两个点之间的距离
            }
            int minLocation = minDistance(distance);
            cluster.get(minLocation).add(dataSet.get(i));// 核心，将当前元素放到最小距离中心的簇中
        }
    }

    /**
     * 求两点误差平方的方法
     *
     * @return 误差平方
     */
    private Integer errorSquare(Integer[] element, Integer[] center) {
        Integer x = element[0] - center[0];
        Integer y = element[1] - center[1];

        Integer errSquare = x * x + y * y;

        return errSquare;
    }

    /**
     * 计算误差平方和准则函数方法
     */
    private void countRule() {
        Integer jcF = 0;
        for (int i = 0; i < cluster.size(); i++) {
            for (int j = 0; j < cluster.get(i).size(); j++) {
                jcF += errorSquare(cluster.get(i).get(j), center.get(i));
            }
        }
        jc.add(jcF);
    }

    /**
     * 设置新的簇中心方法
     */
    private void setNewCenter() {
        for (int i = 0; i < k; i++) {
            int n = cluster.get(i).size();
            if (n != 0) {
                Integer[] newCenter = {0, 0};
                for (int j = 0; j < n; j++) {
                    newCenter[0] += cluster.get(i).get(j)[0];
                    newCenter[1] += cluster.get(i).get(j)[1];
                }
                // 设置一个平均值
                newCenter[0] = newCenter[0] / n;
                newCenter[1] = newCenter[1] / n;
                center.set(i, newCenter);
            }
        }
    }

    /**
     * 打印数据，测试用
     *
     * @param dataArray     数据集
     * @param dataArrayName 数据集名称
     */
    public void printDataArray(ArrayList<Integer[]> dataArray,
                               String dataArrayName) {
        for (int i = 0; i < dataArray.size(); i++) {
            System.out.println("print:" + dataArrayName + "[" + i + "]={"
                    + dataArray.get(i)[0] + "," + dataArray.get(i)[1] + "}");
        }
        System.out.println("===================================");
    }

    /**
     * Kmeans算法核心过程方法
     */
    private void kmeans() {
        init();// 初始化
        printDataArray(dataSet, "initDataSet"); // 输出初始化数据集
        printDataArray(center, "initCenter"); // 输出初始化中心
        // 循环分组，直到误差不变为止
        while (true) {
            clusterSet(); // 生成簇集元素
            // 输出簇集生成结果
            for (int i = 0; i < cluster.size(); i++) {
                printDataArray(cluster.get(i), "cluster[" + i + "]");
            }

            countRule();// 计算误差平方和
            System.out.println("count:" + "jc[" + m + "]=" + jc.get(m));
            System.out.println();
            // 判断退出迭代条件，当最近两次的误差平方和相等，则退出迭代。
            if (m != 0) {
                if (jc.get(m) - jc.get(m - 1) == 0) {
                    break;
                }
            }

            setNewCenter();// 计算新的中心
            printDataArray(center, "newCenter");// 输出新的中心
            m++;
            cluster.clear(); // 簇集清空
            cluster = initCluster(); // 簇集初始化
        }
        System.out.println("note:the times of repeat:m=" + m);// 输出迭代次数
    }

    /**
     * 执行算法
     */
    public void execute() {
        long startTime = System.currentTimeMillis();
        System.out.println("kmeans begins");
        kmeans();
        long endTime = System.currentTimeMillis();
        System.out.println("kmeans running time=" + (endTime - startTime)
                + "ms");
        System.out.println("kmeans ends");
        System.out.println();
    }

    public Map<Integer, ArrayList> calc() {
        //初始化一个Kmean对象，将k置为2
        KMeans k = new KMeans(2);
        ArrayList<Integer[]> dataSet = new ArrayList<>();
        String result = "select DISTINCT  twice,distance from users a left join level b on a.id=b.usersId";
        List<Object[]> message = dao.find(result, null);

        if (message != null && message.size() > 0) {
            for (Object[] data : message) {
                int twice = (Integer) data[0];
                int distance = (Integer) data[1];

                dataSet.add(new Integer[]{twice, distance});
            }
        }
        // 设置原始数据集
        k.setDataSet(dataSet);
        // 执行算法
        k.execute();
        // 得到聚类结果
        ArrayList<ArrayList<Integer[]>> cluster = k.getCluster();
        // 查看结果
        Map<Integer, ArrayList> map = new HashMap<>();
        for (int n = 0; n < cluster.size(); n++) {
            ArrayList arrayList = new ArrayList();
            ArrayList<Integer[]> items = cluster.get(n);
            items.forEach(p -> {
                String sql = "select * from level where twice =" + p[0] + "and distance =" + p[1];
                String args[] = {"id", "usersId", "name", "realname"};
                ArrayList al = sb.select(sql, args);
                arrayList.addAll(al);
            });
            map.put(n, arrayList);
        }
        System.out.println(map);
        return map;
    }

    public static void main(String[] args) {
        KMeans kMeans = new KMeans();
        kMeans.calc();
    }
}